package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/next-greater-element-i/">下一个更大元素 I(Next Greater Element I)</a>
 * <p>nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。</p>
 * <p>给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。</p>
 * <p>对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。</p>
 * <p>返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
 *      输出：[-1,3,-1]
 *      解释：nums1 中每个值的下一个更大元素如下所述：
 *          - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
 *          - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
 *          - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
 *
 * 示例 2：
 *      输入：nums1 = [2,4], nums2 = [1,2,3,4].
 *      输出：[3,-1]
 *      解释：nums1 中每个值的下一个更大元素如下所述：
 *          - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
 *          - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>1 <= nums1.length <= nums2.length <= 1000</li>
 * <li>0 <= nums1[i], nums2[i] <= 104</li>
 * <li>nums1和nums2中所有整数 互不相同</li>
 * <li>nums1 中的所有整数同样出现在 nums2 中</li>
 * </ul>
 * </p>
 *
 * <b>进阶：</b>你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
 *
 * @author c2b
 * @since 2023/4/14 15:58
 */
public class LC0496NextGreaterElement_I_S {

    static class Solution {
        /**
         * 单调栈+hashmap
         * <p>
         * 1.第1个子问题：如何更高效地计算 nums2中每个元素右边的第一个更大的值;<br>
         * 2.第2个子问题：如何存储第1个子问题的结果。
         * </p>
         */
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            Stack<Integer> stack = new Stack<>();
            Map<Integer, Integer> map = new HashMap<>();
            // 从左往右，利用单调栈，找到nums2中最近的右侧的比当前数大的数，维护到map中
            for (int i = nums2.length - 1; i >= 0; --i) {
                // 将栈中所有小于等于当前数的数弹出栈
                while (!stack.isEmpty() && nums2[i] >= stack.peek()) {
                    stack.pop();
                }
                // 此时栈中的元素即为满足条件的数
                map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
                stack.push(nums2[i]);
            }
            // 只需要从map获取右侧比当前数大的数作为结果即可
            int[] res = new int[nums1.length];
            for (int i = 0; i < nums1.length; i++) {
                res[i] = map.get(nums1[i]);
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.nextGreaterElement(new int[]{2, 4}, new int[]{1, 2, 3, 4}));
    }
}
